/*
 * @Author: 缄默
 * @Date: 2022-03-16 20:46:11
 * @LastEditors: 缄默
 * @LastEditTime: 2022-03-16 22:29:29
 */

//在有序但含有空的数组中查找字符串

#include <iostream>
#include <string>

using namespace std;

int getIndex(const string& strs, const char str);

int main() {
    string strs = " a a b c";
    char str1 = 'a';
    char str2 = ' ';
    char str3 = 'd';
    cout << "str1: " << getIndex(strs, str1) << endl;
    cout << "str2: " << getIndex(strs, str2) << endl;
    cout << "str3: " << getIndex(strs, str3) << endl;

    return 0;
}

int getIndex(const string& strs, const char str) {
    if (str == ' ') return -1;
    int left = 0;
    int right = strs.size() - 1;
    int mid = (left + right) / 2;
    int res = -1;
    int mids = 0;
    while (left <= right) {
        mid = (right + left) / 2;
        //先从好判断的入手 
        //不为空且相等
        if (strs[mid] != ' ' && strs[mid] == str) {
            res = mid;
            right = mid - 1;
        } 
        //不为空的话判断左右 因为相邻为null 所以可以直接加1
        else if (strs[mid] != ' ') {
            if (strs[mid] < str) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } 
        //下面的与上面的同理
        else {
            mids = mid;
            while (strs[mids] == ' ' && --mids > left) ;
            if (mids < left || strs[mids] < str) {
                left = mid + 1;
            } else {
                res = strs[mids] == str ? mids : res;
                right = mids - 1;
            }

        }

    }
    return res;

}
